[LeetCode]1.TwoSum(Python实现)

您所在的位置:网站首页 leetcode 3 python [LeetCode]1.TwoSum(Python实现)

[LeetCode]1.TwoSum(Python实现)

2023-10-22 09:03| 来源: 网络整理| 查看: 265

1.题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 2.代码实现

1. 方法一:

[分析]:        自然而然的想法,首先用for循环对nums数组进行遍历,从第一个元素开始,然后再查找数组中有没有target-nums[i]这个元素;有的话,则返回当前元素下标与另一个元素的下标,作为结果输出。代码如下:

class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): if (target - nums[i]) in nums: return [i,nums.index(target - nums[i])]

        然而,实际编程过程中出现了这么一个问题,Python提供的list.index(value,from,to) “左闭右开区间”,在不指定from,to的时候,该方法默认返回数组中第一次出现该value的index值,在case([3,4,2],6)中,应该输出[1,2],而按照前面的思路,直接输出了[0,0],这显然是不正确的,于是直接的想法是比较两个元素对应的index是否相等,是的话,就pass掉,代码改为如下:

class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): if (target - nums[i]) in nums: idx = nums.index(target - nums[i]) if i == idx: pass else: return [i,idx]

       然而,还是出了问题,比如说在case([0,3,4,0],0)中,应该输出[0,3],但上面方法却输出了null,我的一个新思路是,是不是应该在查找 target - nums[i] 元素的index时,设定一个from值,应该从当前元素的后面一个开始查找元素,于是代码改为如下:

class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): if (target - nums[i]) in nums: idx = nums.index(target - nums[i],i+1) # 这里设置了from return [i,idx]

       如此一来,貌似解决了case([0,3,4,0],0)的问题,结果运行的时候,case([3,4,2],6)发生运行错误,程序在执行第一个元素的时候,查找到nums里有(6-3),但是在搜index的时候,由于设置了搜索范围,查找不到元素3的索引,可谓是顾此失彼。        没办法,只能继续思考,如何解决这个两难的问题,突然一个想法产生,我何不对nums数组进行切片呢?即我在判断数组中是否包含 target - nums[i] 元素时,不应该对整个数组进行查找,而是应该对num[i+1:]进行查找,代码如下:

class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): num = target - nums[i] if num in nums[i+1:]: return [i, nums.index(num,i+1)]

       最终程序测试结果:        执行用时804ms,战胜64.84%的python提交记录,这说明我的算法还有很大的提升空间,时间复杂度为O(n^2),for循环的复杂度为O(n), x in list方法的复杂度为O(n),取切片的复杂度为O(k),index的方法为O(n),这里复杂度的计算参考了官网。        这里我偷懒了,直接在网上找了别人的优秀算法,看完之后,惊为天人,在方法二中来进行说明。

2.方法二:        先看代码:

class Solution(object): def twoSum(self, nums, target): nums_dict = {} for i, num in enumerate(nums): if num in nums_dict: return [nums_dict[num], i] else: nums_dict[target - num] = i

       代码思路:这个算法的核心思想是构造一个字典,字典用来存储当前元素完成target需要的元素值作为key,当前元素的index作为value。然后遍历过程中进行判断,当前元素是不是属于我想要的元素,是的话,直接输出 [字典中该元素的下标,当前遍历元素下标]        思考:这个算法快在哪里?        从时间复杂度的角度来看,第一层for循环是O(n),字典采用的是hash函数的结构,所以在 x in dict的查找过程中,时间复杂度为O(1),而这里没用到index查询,而是直接获取value值,而字典的Get Item的复杂度也是O(1),所以整个算法的时间复杂度为O(n),不过这里的空间复杂度是O(n),用空间换时间。        最终程序测试结果:



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3